package 纯数组;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class NC54数组中相加为0的三元组 {

    /**
     * 给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
     * 注意：
     * 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
     * 解集中不能包含重复的三元组。
     * 例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)
     */

    //快排+指针查找(禁止二分,因为可能会跳过解)
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

        ArrayList<ArrayList<Integer>> result=new ArrayList<>();

        if(num.length<3){
            return result;
        }

        //直接排序(杜绝重复元素)后双指针搞起

        Arrays.sort(num);
        int left;
        int right;
        int leftNum;
        int rightNum;
        int sum;

        for (int i = 0; i < num.length - 2; i++) {
            if(num[i]>0){
                break;
            }
            if(i>=1&&num[i]==num[i-1]){
                continue;//相同的跳过
            }
            left=i+1;
            right=num.length-1;
            while (left<right){
                leftNum=num[left];
                rightNum=num[right];
                sum=leftNum+rightNum;
                if(num[i]+sum==0){
                    //符合条件
                    ArrayList<Integer> arrayList=new ArrayList<>();
                    arrayList.add(num[i]);
                    arrayList.add(num[left]);
                    arrayList.add(num[right]);
                    result.add(arrayList);
                    //注意数组是排序好数字,下一个答案必在中间区域
                    left++;
                    //去除重复元素
                    while (left<right&&num[left]==num[left-1]){
                        left++;
                    }
                    right--;
                    //去除重复元素
                    while (left<right&&num[right]==num[right+1]){
                        right--;
                    }
                }else if(sum+num[i]>0){
                    //右指针左移
                    right--;
                }else{
                    //左指针右移动
                    left++;
                }
            }

        }

        return result;
    }

    public static void main(String[] args) {
        NC54数组中相加为0的三元组 n=new NC54数组中相加为0的三元组();
        ArrayList<ArrayList<Integer>> result = n.threeSum(new int[]{1,-1,-1,0});
        System.out.println(JSON.toJSONString(result));
    }

}
